package DataStructures.sort;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author ：ALi
 * @date ：Created in 2021/11/18 21:05
 * @description：桶排序
 * @modified By：
 * @version: $
 */
public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {53,3,542,748,14,214};
        int[] res = new int[arr.length];
        res = sort(arr);
        System.out.println(Arrays.toString(res));
    }

    public static int[] sort(int[] array){

        //定义桶，bucket[i][j]表示第i个桶的第j个元素
        int[][] bucket = new int[10][array.length];

        //统计一个桶中的元素个数，方便将元素取出来
        int[] bucketElementCount = new int[bucket.length];

        int max = 0;
        for (int i = 0;i< array.length;i++){
            if(max < array[i]){
                max = array[i];
            }
        }
        //最大数的位数
        int maxLeng = (max+"").length();


        for (int i = 0,n = 1;i<maxLeng;i++,n=n*10){
            //根据位数的将数据放入相应的桶中
            for(int j = 0;j<array.length;j++){
                int bucketIndex = array[j]/n%10;
                bucket[bucketIndex][bucketElementCount[bucketIndex]] = array[j];
                bucketElementCount[bucketIndex]++;
            }
            //将桶中的元素放入到arr中,并将桶中元素的总个数置为0
            int index = 0;

            for (int l = 0;l<bucket.length;l++){
                if(bucketElementCount[l] != 0){
                    for (int k = 0;k<bucketElementCount[l];k++){
                        array[index] = bucket[l][k];
                        index++;
                    }
                }
                bucketElementCount[l] = 0;

            }

        }




        return array;
    }

}